package com.shuang.hash7;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {

    public List<List<Integer>> threeSum(int[] nums) {
        //双指针方法
        //现将数组排序（升序） 循环索引i从零开始 left指向i+1 right指向结尾位置
        //如果三个数相加和大于零证明数大了 将right向左移动一位 和小于零将left向右移动一位
        //去重处理 第一个数去重 要比较前一位（nums[i] 和 nums[i-1]比较）如果重复 跳出这次循环，如果比较后一位（nums[i] 和 nums[i+1]比较）的话会出现有两个数重复就直接跳出此次循环了并没有将此次三个数保存起来 例如[-1, -1, 2]
        //第二个和第三个数去重 都在保存完一组三个数之后进行处理即可

        //将数组排序
        Arrays.sort(nums);

        //定义用于封装结果的集合
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length; i++){

            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以
            if (nums[i] > 0) {
                return res;
            }

            //定义左右指针位置
            int left = i + 1;
            int right = nums.length - 1;

            //去重第一个数
            if (i > 0 && nums[i] == nums[i - 1]){
                continue; //跳出本次循环
            }

            //进行加法计算
            int sum = 0;
            while (left < right){
                sum = nums[i] + nums[left] + nums[right];
                if (sum < 0){
                    left++;
                }else if (sum > 0){
                    right--;
                }else {
                    //证明这三个数可以保存
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    //保存完一组结果后要对第二个和第三个数进行去重
                    while (right > left && nums[left] == nums[left + 1]){
                        left++;  //left的下一个数跟之前的相等 跳过此次这个数
                    }

                    while (right > left && nums[right] == nums[right - 1]){
                        right--;  //跳过这个数
                    }

                    //去重之后 左右指针各移动一步
                    left++;
                    right--;
                }
            }
        }

        //for循环结束返回结果
        return res;
    }
}
